#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
//string s[5][5];
//bool vis[5][5];
//string ans;
//int dx[8] = { -1,-1,-1,0,0,1,1,1 };
//int dy[8] = { -1,0,1,-1,1,-1,0,1 };
//
//
//string cmp(string a, string b) {
//	if (a.size() == 0)
//		return b;
//	if (a[0] != b[0]) {
//		if (a[0] > b[0])
//			return b;
//		else 
//			return a;
//	}
//	else if (a[1] != b[1]) {
//		if (a[1] > b[1])
//			return b;
//		else
//			return a;
//	}
//	else {
//		if (a[2] >= b[2])
//			return b;
//		else
//			return a;
//	}
//}
//
//void dfs(int x, int y, int n,string ok) {
//	if (ok.size()==3) {
//		ans = cmp(ans, ok);
//		return;
//	}
//	for (int i = 0; i < 8; i++) {
//		int xx = x + dx[i], yy = y + dy[i];
//		if (xx > 0 && xx <= 3 && yy > 0 && yy <= 3 && !vis[xx][yy]) {
//			string tmp = ok+s[xx][yy];
//			vis[xx][yy] = true;
//			dfs(xx, yy, n + 1,tmp);
//			vis[xx][yy] = false;
//		}
//	}
//}
//
//int main() {
//	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//	for (int i = 1; i <= 3; i++) {
//		for (int j = 1; j <= 3; j++) {
//			char c;
//			cin >> c;
//			s[i][j] = string(1, c);
//		}
//	}
//
//	for (int i = 1; i <= 3; i++) {
//		for (int j = 1; j <= 3; j++) {
//			vis[i][j] = true;
//			dfs(i, j, 1,s[i][j]);
//			vis[i][j] = false;
//		}
//	}
//	cout << ans << '\n';
//	return 0;
//}


//const int mod = 1e9 + 7;
//int t;
//int n, m;
//ll f[2000006];
//
//ll qp(ll a, ll b) {
//	ll res = 1, base = a;
//	while (b > 0) {
//		if (b & 1)res = (res * base) % mod;
//		base = (base * base) % mod;
//		b >>= 1;
//	}
//	res %= mod;
//	return res;
//}
//
//
//int main() {
//	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//	f[0] = 1;
//	for (int i = 1; i <= 2000005; i++) {
//		f[i] = (f[i - 1] * i) % mod;
//	}
//	cin >> t;
//	while (t--) {
//		cin >> n >> m;
//		if (n < m) {
//			int tmp = m;
//			m = n;
//			n = tmp;
//		}
//		ll ans = f[n + m];
//		ll tmp1 = qp(f[m], mod - 2);
//		ll tmp2 = qp(f[n], mod - 2);
//		ans = (((ans * tmp1) % mod) * tmp2) % mod;
//		cout << ans<<'\n';
//	}
//	return 0;
//}


//ll a, N;
//vector <int> p;
//bool v[1000006];
//ll ans, x, y;
//ll gcd(ll x, ll y) {
//	return y ? gcd(y, x % y) : x;
//}
//ll exgcd(ll a, ll b, ll& x, ll& y) {
//	if (!b) {
//		x = 1;
//		y = 0;
//		return a;
//	}
//	ll d = exgcd(b, a % b, x, y);
//	ll z = x; x = y; y = z - y * (a / b);
//	return d;
//}
//int main() {
//	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//	cin >> a >> N;
//	for (int i = 2; i <= N; i++) {
//		if (!v[i]) { p.push_back(i); }
//		for (int j:p) {
//			if (i * j > N)break;
//			v[i * j] = true;
//			if (i % j == 0)
//				break;
//		}
//	}
//	if (p.size() == 0) {
//		cout << 0;
//		return 0;
//	}
//	for (auto b : p) {
//		if (gcd(b, a) != 1)
//			continue;
//		exgcd(a, b, x, y);
//		ans += (x % b + b) % b;
//	}
//	cout << ans;
//	return 0;
//}
//
//int n, m,l;
//long long dis[200005];
//bool vis[200005];
//long long wei[200005];
//vector<pair<long long,long long>>e[200005];
//const int mod = 1e9 + 7;
//ll ans;
//struct node
//{
//	ll dis, pos;
//	bool operator<(const node& x) const {
//		return x.dis < dis;
//	}
//};
//
//priority_queue<node> q;
//
//int main() {
//	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//	cin >> n >> m >> l;
//	for (ll i = 1,x; i <= n; i++) {
//		cin >> x;
//		wei[i] = x;
//		dis[i] = 1e9;
//	}
//	for (ll i = 1,x; i <= m; i++) {
//		cin >> x;
//		e[1].push_back({ x,0 });
//	}
//	dis[1] = 0;
//	q.push({ 0,1 });
//	for (ll i = 0,v,u,w; i < l; i++) {
//		cin >> u >> v >> w;
//		e[u].push_back({ v,w });
//		e[v].push_back({ u,w });
//	}
//	while (!q.empty()) {
//		node tmp = q.top();
//		ll u = tmp.pos;
//		q.pop();
//		if (vis[u])continue; vis[u] = 1;
//		for (ll i = 0; i < e[u].size(); i++) {
//			ll v = e[u][i].first;
//			ll w = e[u][i].second;
//			if (!vis[v] && dis[u] + w < dis[v]) {
//				dis[v] = dis[u] + w;
//				q.push({ dis[v],v });
//			}
//		}
//	}
//	for (ll i = 2; i <= n; i++) {
//		ans = ((ans + (dis[i]%mod * wei[i]) % mod) % mod);
//	}
//	cout << ans<<'\n';
//	return 0;
//}
//

class Sum {
private:
    static int _i;
    static int _ret;
public:
    Sum() {
        _ret += _i;
        _i++;
    }
    static int Getret() {
        return _ret;
    }
};

int Sum::_i = 1;
int Sum::_ret = 0;


class Solution {
public:
    int Sum_Solution(int n) {
        Sum a[n];
        return Sum::Getret();
    }
};

